package search

import "fmt"

// InsertSearch 插值查找
func InsertSearch(arr []int, target int) int {
	return sea(arr, target, 0, len(arr)-1)
}

func sea(arr []int, target, start, end int) int {
	midPtr := start + (end-start)*(target-arr[start])/(arr[end]-arr[start])
	counter := 0

	for midPtr := midPtr; start <= end; midPtr = start + (end-start)*(target-arr[start])/(arr[end]-arr[start]) {
		counter++
		if arr[midPtr] == target {
			fmt.Println(counter)
			return midPtr
		}
		if arr[midPtr] > target {
			end = midPtr - 1
		} else {
			start = midPtr + 1
		}
	}
	fmt.Println(counter)
	return -1
}
